package com.freedy.dataStructure.graph;

import java.util.*;

/**
 * 邻接矩阵实现图
 *
 * @author Freedy
 * @date 2021/4/4 14:01
 */
public class AdjacencyMatrixGraph {
    private final List<String> vertexList;//存储顶点的集合
    private final int[][] edges;//存储图的邻接矩阵
    private final boolean[] isVisited;
    private int numOfEdge;//边的数目

    public AdjacencyMatrixGraph(int n) {
        vertexList = new ArrayList<>(n);
        edges = new int[n][n];
        isVisited = new boolean[n];
        numOfEdge = 0;
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     *
     * @param v1     第一个顶点的下标
     * @param v2     第二个顶点的下标
     * @param weight 权值
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdge++;
    }

    /**
     * @return 节点的个数
     */
    public int size() {
        return vertexList.size();
    }

    /**
     * @return 返回边的数目
     */
    public int getNumOfEdge() {
        return numOfEdge;
    }

    /**
     * @param i 索引
     * @return 指定索引所对应的数据
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    /**
     * @param v1 第一个顶点的下标
     * @param v2 第二个顶点的下标
     * @return 两点之间的权值
     */
    public int getWight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 打印图
     */
    public void printGraph() {
        for (int i = -1; i < edges.length; i++) {
            for (int j = -1; j < edges.length; j++) {
                if (i == -1) {
                    System.out.print(j == -1 ? "  " : vertexList.get(j) + " ");
                } else {
                    System.out.print(j == -1 ? vertexList.get(i) + " " : edges[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    /**
     * 使用深度优先遍历的方法,来遍历图
     */
    public void DFS() {
        //重置isVisited数组
        Arrays.fill(isVisited, false);
        //考虑到非联通图 需要对每个点进行深度遍历
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                DFS(i);
            }
        }
        System.out.println();
    }

    /**
     * 使用广度优先遍历的方法,来遍历图
     */
    public void BFS(){
        //重置isVisited数组
        Arrays.fill(isVisited, false);
        //考虑到非联通图 需要对每个点进行深度遍历
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                BFS(i);
            }
        }
        System.out.println();
    }

    /**
     * 深度优先遍历
     */
    private void DFS(int index) {
        isVisited[index] = true;
        System.out.print(vertexList.get(index) + "->");
        for (int i = 0; i < edges.length; i++) {
            if (edges[index][i] != 0) {
                if (!isVisited[i]) {
                    DFS(i);
                }
            }
        }
    }

    /**
     * 广度优先遍历
     */
    private void BFS(int index) {
        //队列，记录节点访问的顺序
        LinkedList<Integer> queue = new LinkedList<>();
        isVisited[index] = true;
        System.out.print(vertexList.get(index)+"->");
        queue.addLast(index);
        while (!queue.isEmpty()){
            Integer pop = queue.pop();
            for (int i = 0; i < edges.length; i++) {
                if (edges[pop][i] != 0) {
                    if (!isVisited[i]) {
                        isVisited[i] = true;
                        System.out.print(vertexList.get(i)+"->");
                        queue.addLast(i);
                    }
                }
            }
        }
    }

}
